{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上一节推导出了$P_w(y\\mid x)$求解的矩阵形式，这将会为后续的相关计算提供很大的便捷，但在此之前我们还有一根刺需要拔掉，那就是特征函数，根据上一节的推导知道，特征函数应该长这个样子：   \n",
    "\n",
    "$$\n",
    "f_k(y_{i-1},y_i,x,i)\n",
    "$$  \n",
    "\n",
    "它是关于$(y_{i-1},y_i,x,i)$的函数，那它通常如何定义呢？下面我就结合[CRF++的模板定义](http://taku910.github.io/crfpp/)以及[知乎上的例子](https://www.zhihu.com/question/20279019)进行说明"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一.模板定义\n",
    "crf++中的模板定义语句为%x[row,col]，其中row表示选择的观测特征对当前位置的偏移量，col表示所选观测特征的所在列，下面用一个例子做说明，比如我们有如下用作分词训练的语料，其中第0列和第1列是可观测数据（$x$），第2列即是我们的标签数据（$y$）:    \n",
    "\n",
    "|字|词性|分词标记|\n",
    "|  ----  | ----  |----  |\n",
    "| 北  | N  |B  |\n",
    "| 京  | N  |E  |\n",
    "| 欢  | V  |B  |\n",
    "| 迎  | V  |M  |\n",
    "| 你  | E  |E  |\n",
    "\n",
    "假设，我们目前的位置在“欢”所在行，即$i=3$，那么按照模板定义，我们可以获取相应的特征取值：   \n",
    "\n",
    "|模板|取值|\n",
    "|  ----  | ----  |\n",
    "| %x[0,0]\t  | 欢  |\n",
    "| %x[0,1]  | V  |\n",
    "| %x[-1,0]  | 京  |\n",
    "| %x[-2,1]  | N  |\n",
    "| %x[2,1]  | E  |\n",
    "| %%x[0,0]/%x[0,1]\t  | 欢/V  |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二.unigram模板\n",
    "unigram模板对应我们上一节的状态特征函数$s_l(y_i,x,i)$，对应模板格式为**U+id+模板定义**，比如U01:%x[0,0]，每一行模板会生成一组状态特征函数，数量为$L\\times N$，$L$是标签状态数，$N$是所在列特征集的数量，比如模板U01:%x[0,0]，就会有$3\\times 5=15$个特征函数，其中标签状态有{B,E,M},所在列特征集有{北,京,欢,迎,你}，那么构成的15个特征函数如下：  \n",
    "\n",
    "```\n",
    "func1 = if (output = B and feature=U01:\"北\") return 1 else return 0   \n",
    "func2 = if (output = M and feature=U01:\"北\") return 1 else return 0   \n",
    "func3 = if (output = E and feature=U01:\"北\") return 1 else return 0   \n",
    "func4 = if (output = B and feature=U01:\"京\") return 1 else return 0   \n",
    "...   \n",
    "func13 = if (output = B and feature=U01:\"你\") return 1 else return 0   \n",
    "func14 = if (output = M and feature=U01:\"你\") return 1 else return 0   \n",
    "func15 = if (output = E and feature=U01:\"你\") return 1 else return 0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三.bigram模板\n",
    "bigram模板对应我们上一节的状态特征函数$t_k(y_{i-1},y_i,x,i)$，它会比unigram模板多考虑一个上一标签状态，所以对每一行模板它会产生$L\\times L\\times N$个特征函数，比如对于B01:%x[0,0]，对应的特征函数有：   \n",
    "```\n",
    "func1 = if (prev_output = B and output = B and feature=B01:\"北\") return 1 else return 0   \n",
    "func2 = if (prev_output = B and output = E and feature=B01:\"北\") return 1 else return 0  \n",
    "func3 = if (prev_output = B and output = M and feature=B01:\"北\") return 1 else return 0  \n",
    "func4 = if (prev_output = M and output = E and feature=B01:\"北\") return 1 else return 0  \n",
    "...   \n",
    "func44 = if (prev_output = M and output = E and feature=B01:\"你\") return 1 else return 0  \n",
    "func45 = if (prev_output = E and output = E and feature=B01:\"你\") return 1 else return 0  \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 四. CoNLL 2000例子\n",
    "我们看一下 CoNLL 2000模板的例子：   \n",
    "\n",
    "```\n",
    "# Unigram\n",
    "U00:%x[-2,0]\n",
    "U01:%x[-1,0]\n",
    "U02:%x[0,0]\n",
    "U03:%x[1,0]\n",
    "U04:%x[2,0]\n",
    "U05:%x[-1,0]/%x[0,0]\n",
    "U06:%x[0,0]/%x[1,0]\n",
    "\n",
    "U10:%x[-2,1]\n",
    "U11:%x[-1,1]\n",
    "U12:%x[0,1]\n",
    "U13:%x[1,1]\n",
    "U14:%x[2,1]\n",
    "U15:%x[-2,1]/%x[-1,1]\n",
    "U16:%x[-1,1]/%x[0,1]\n",
    "U17:%x[0,1]/%x[1,1]\n",
    "U18:%x[1,1]/%x[2,1]\n",
    "\n",
    "U20:%x[-2,1]/%x[-1,1]/%x[0,1]\n",
    "U21:%x[-1,1]/%x[0,1]/%x[1,1]\n",
    "U22:%x[0,1]/%x[1,1]/%x[2,1]\n",
    "\n",
    "# Bigram\n",
    "B\n",
    "```  \n",
    "\n",
    "这里B表示只考虑了前一个标签状态和当前标签状态，而不考虑当前特征取值的情况，它的特征函数形如：   \n",
    "```\n",
    "func = if (prev_output = M and output = E) return 1 else return 0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 五.代码实现\n",
    "好哒，让我们自己来实现一把特征函数的生成吧，这里为了方便，就只考虑只有一种特征的情况，对比上面的例子就是用“字”去预测是否“切分”，而不考虑“词性”，即标准CRF中$P(Y\\mid X)$的情况，而CRF++可以支持扩展到$P(Y\\mid X_1,X_2,...,X_n)$的情况（这里$X_i$是与$Y$一一对应的队列）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "\"\"\"\n",
    "线性链条件随机场的实现，封装到ml_models.pgm\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "1.实现特征函数的功能\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class CRFFeatureFunction(object):\n",
    "    def __init__(self, unigram_rulers=None, bigram_rulers=None):\n",
    "        \"\"\"\n",
    "        默认输入特征就一种类型\n",
    "        :param unigram_rulers: 状态特征规则\n",
    "        :param bigram_rulers: 状态转移规则\n",
    "        \"\"\"\n",
    "        if unigram_rulers is None:\n",
    "            self.unigram_rulers = [\n",
    "                [0],  # 当前特征->标签\n",
    "                [1],  # 后一个特征->标签\n",
    "                [-1],  # 前一个特征->标签\n",
    "                [0, 1],  # 当前特征和后一个特征->标签\n",
    "                [-1, 0]  # 前一个特征和当前特征->标签\n",
    "            ]\n",
    "        else:\n",
    "            self.unigram_rulers = unigram_rulers\n",
    "        if bigram_rulers is None:\n",
    "            self.bigram_rulers = [\n",
    "                None,  # 不考虑当前特征，只考虑前一个标签和当前标签\n",
    "                [0]  # 当前特征->前一个标签和当前标签\n",
    "            ]\n",
    "        else:\n",
    "            self.bigram_rulers = bigram_rulers\n",
    "        # 特征函数\n",
    "        self.feature_funcs = []\n",
    "\n",
    "    def fit(self, x, y):\n",
    "        \"\"\"\n",
    "        构建特征函数，为了节省空间，训练集x,y中没有出现的特征和标签组合就不考虑了\n",
    "        :param x: [[...],[...],...,[...]]\n",
    "        :param y: [[...],[...],...,[...]]\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        uni_cache = {}\n",
    "        bi_cache = {}\n",
    "        for i in range(0, len(x)):\n",
    "            xi = x[i]\n",
    "            yi = y[i]\n",
    "            # 处理unigram_ruler\n",
    "            for k, unigram_ruler in enumerate(self.unigram_rulers):\n",
    "                if uni_cache.get(k) is None:\n",
    "                    uni_cache[k] = []\n",
    "                for j in range(max(0, 0 - np.min(unigram_ruler)), min(len(xi), len(xi) - np.max(unigram_ruler))):\n",
    "                    key = \"\".join(str(item) for item in [xi[pos + j] for pos in unigram_ruler] + [yi[j]])\n",
    "                    if key in uni_cache[k]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        self.feature_funcs.append([\n",
    "                            'u',\n",
    "                            unigram_ruler,\n",
    "                            [xi[j + pos] for pos in unigram_ruler],\n",
    "                            yi[j]\n",
    "                        ])\n",
    "                        uni_cache[k].append(key)\n",
    "            # 处理 bigram_ruler\n",
    "            for k, bigram_ruler in enumerate(self.bigram_rulers):\n",
    "                if bi_cache.get(k) is None:\n",
    "                    bi_cache[k] = []\n",
    "                # B的情况\n",
    "                if bigram_ruler is None:\n",
    "                    for j in range(1, len(xi)):\n",
    "                        key = \"B\" + \"\".join([str(yi[j - 1]), str(yi[j])])\n",
    "                        if key in bi_cache[k]:\n",
    "                            continue\n",
    "                        else:\n",
    "                            self.feature_funcs.append([\n",
    "                                'B',\n",
    "                                None,\n",
    "                                None,\n",
    "                                [yi[j - 1], yi[j]]\n",
    "                            ])\n",
    "                            bi_cache[k].append(key)\n",
    "                    continue\n",
    "                # 非B的情况\n",
    "                for j in range(max(1, 0 - np.min(bigram_ruler)), min(len(xi), len(xi) - np.max(bigram_ruler))):\n",
    "                    key = \"\".join(str(item) for item in [xi[pos + j] for pos in bigram_ruler] + [yi[j - 1], yi[j]])\n",
    "                    if key in bi_cache[k]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        self.feature_funcs.append([\n",
    "                            'b',\n",
    "                            bigram_ruler,\n",
    "                            [xi[j + pos] for pos in bigram_ruler],\n",
    "                            [yi[j - 1], yi[j]]\n",
    "                        ])\n",
    "                        bi_cache[k].append(key)\n",
    "        del uni_cache\n",
    "        del bi_cache\n",
    "\n",
    "    def map(self, y_pre, y_cur, x_tol, i_cur):\n",
    "        \"\"\"\n",
    "        返回是否match特征函数的list\n",
    "        :param y_pre:\n",
    "        :param y_cur:\n",
    "        :param x_tol:\n",
    "        :param i_cur:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def map_func_(func):\n",
    "            try:\n",
    "                gram_type, ruler, xi, yi = func\n",
    "                if gram_type == \"u\" and [x_tol[i + i_cur] for i in ruler] == xi and yi == y_cur:\n",
    "                    return 1\n",
    "                elif gram_type == \"b\" and [x_tol[i + i_cur] for i in ruler] == xi and yi == [y_pre, y_cur]:\n",
    "                    return 1\n",
    "                elif gram_type == \"B\" and yi == [y_pre, y_cur]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            except:\n",
    "                # 越界的情况，默认不匹配\n",
    "                return 0\n",
    "\n",
    "        return np.asarray(list(map(map_func_, self.feature_funcs)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "31\n",
      "[0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0]\n"
     ]
    }
   ],
   "source": [
    "# 测试\n",
    "x = [[\"我\", \"爱\", \"我\", \"的\", \"祖\", \"国\"], [\"我\", \"爱\"]]\n",
    "y = [[\"B\", \"E\", \"B\", \"E\", \"B\", \"E\"], [\"B\", \"E\"]]\n",
    "ff = CRFFeatureFunction()\n",
    "ff.fit(x, y)\n",
    "print(len(ff.feature_funcs))\n",
    "print(ff.map(\"B\", \"E\", [\"我\", \"爱\", \"我\", \"的\"], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`feature_funcs`表示特征函数的列表，`map`函数计算当前数据与特征函数集的匹配情况，1表示匹配上，0表示未匹配上"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
